﻿//class Solution {
//public:
//    int minSubArrayLen(int target, vector<int>& nums) {
//        int ret = INT_MAX, n = nums.size();
//        for (int left = 0, right = 0, sum = 0; right < n; right++)
//        {
//            sum += nums[right];//进窗口
//            while (sum >= target)//判断
//            {
//                //更新结果
//                ret = min(ret, right - left + 1);
//                sum -= nums[left++];
//            }
//        }
//        return ret == INT_MAX ? 0 : ret;
//    }
//};


//class Solution {
//public:
//    int lengthOfLongestSubstring(string s) {
//        int hash[128] = { 0 };//数组模拟哈希表，用于判断重复字符
//        int ret = 0, n = s.size();
//        for (int left = 0, right = 0; right < n; right++)
//        {
//            hash[s[right]]++;//进窗口
//            while (hash[s[right]] >= 2)//判断
//            {
//                //出窗口
//                hash[s[left++]]--;
//            }
//            //更新结果
//            ret = max(ret, right - left + 1);
//        }
//        return ret;
//    }
//};


//class Solution {
//public:
//    int longestOnes(vector<int>& nums, int k) {
//        int ret = 0, count = 0, n = nums.size();//统计0个数
//        for (int left = 0, right = 0; right < n; right++)
//        {
//            if (nums[right] == 0)
//                count++;
//            //判断，出窗口
//            while (count > k)
//            {
//                if (nums[left] == 0)
//                {
//                    count--;
//                }
//                left++;
//            }
//            //更新结果
//            ret = max(ret, right - left + 1);
//        }
//        return ret;
//    }
//};


//class Solution {
//public:
//    int minOperations(vector<int>& nums, int x) {
//        //统计总和,将问题转化为求最大连续操作数的和为sum-x
//        int total = 0;
//        for (auto e : nums)
//        {
//            total += e;
//        }
//        int target = total - x;
//        if (target < 0)
//            return -1;
//
//        int len = -1, sum = 0;
//        for (int left = 0, right = 0, n = nums.size(); right < n; right++)
//        {
//            sum += nums[right];//进窗口
//            while (sum > target)
//            {
//                //出窗口
//                sum -= nums[left++];
//            }
//            //更新结果
//            if (sum == target)
//                len = max(len, right - left + 1);
//        }
//        return len == -1 ? -1 : nums.size() - len;
//    }
//};


//class Solution {
//public:
//    int numSubarraysWithSum(vector<int>& nums, int goal) {
//        int n = nums.size();
//        int left1 = 0, left2 = 0, right = 0;
//        int sum1 = 0, sum2 = 0;
//        int ret = 0;
//        while (right < n) 
//        {
//            sum1 += nums[right];
//            while (left1 <= right && sum1 > goal)
//            {
//                sum1 -= nums[left1];
//                left1++;
//            }
//            sum2 += nums[right];
//            while (left2 <= right && sum2 >= goal) 
//            {
//                sum2 -= nums[left2];
//                left2++;
//            }
//            ret += left2 - left1;
//            right++;
//        }
//        return ret;
//    }
//};


//class Solution {
//    int cnt[3];
//public:
//    int numberOfSubstrings(string s) 
//    {
//        int len = (int)s.length(), ans = 0;
//        cnt[0] = cnt[1] = cnt[2] = 0;
//        for (int l = 0, r = -1; l < len;)
//        {
//            while (r < len && !(cnt[0] >= 1 && cnt[1] >= 1 && cnt[2] >= 1))
//            {
//                if (++r == len) break;
//                cnt[s[r] - 'a']++;
//            }
//            ans += len - r;
//            cnt[s[l++] - 'a']--;
//        }
//        return ans;
//    }
//};

class Solution
{
public:
	vector<int> findAnagrams(string s, string p)
	{
		vector<int> ret;
		int hash1[26] = { 0 }; // 统计字符串 p 中每个字符出现的个数
		for (auto ch : p) hash1[ch - 'a']++;
		int hash2[26] = { 0 }; // 统计窗⼝⾥⾯的每⼀个字符出现的个数
		int m = p.size();
		for (int left = 0, right = 0, count = 0; right < s.size(); right++)
		{
			char in = s[right];
			// 进窗⼝ + 维护 count
			if (++hash2[in - 'a'] <= hash1[in - 'a']) count++;
			if (right - left + 1 > m) // 判断
			{
				char out = s[left++];
				// 出窗⼝ + 维护 count
				if (hash2[out - 'a']-- <= hash1[out - 'a']) count--;
			}
			// 更新结果
			if (count == m) ret.push_back(left);
		}
		return ret;
	}
};
